use regex::Regex;
use std::sync::LazyLock;

pub fn convert_base(num_str: &str, to_base: u32) -> String {
    assert!(to_base >= 2 && to_base <= 16);

    let num = Num::parse(num_str).expect("Parse number string");

    let mut digits = Vec::new();
    let mut last_quotient = num;
    loop {
        let (q, r) = last_quotient.divide(to_base as u8);
        digits.insert(0, r);
        if q.is_zero() {
            break;
        }
        last_quotient = q;
    }

    digits
        .into_iter()
        .map(|d| char::from_digit(d as u32, to_base).unwrap())
        .collect()
}

/// Represents an arbitrary number in a specified base.
#[derive(Debug, Clone, PartialEq)]
pub struct Num {
    // Every digit should be in [0, base)
    digits: Vec<u8>,
    base: u8,
}

impl Num {
    pub fn zero(base: u8) -> Num {
        Num {
            digits: vec![0],
            base,
        }
    }

    pub fn is_zero(&self) -> bool {
        self.digits.len() == 1 && self.digits[0] == 0
    }

    pub fn parse(s: &str) -> Result<Num, String> {
        static NUM_REG: LazyLock<Regex> =
            LazyLock::new(|| Regex::new(r"^(\w+)\((\w+)\)$").unwrap());

        let (digit_part, base_part) = match NUM_REG.captures(s) {
            Some(caps) => (caps.get(1).unwrap().as_str(), caps.get(2).unwrap().as_str()),
            None => {
                return Err("invalid number string, expected format `<digits>(<base>)`".to_owned())
            }
        };

        let base = base_part.parse::<u8>().map_err(|e| e.to_string())?;
        if base < 2 || base > 16 {
            return Err(format!("unsupported base '{base}'"));
        }

        let mut digits = Vec::new();
        for c in digit_part.chars() {
            let d = match c.to_digit(base as u32) {
                Some(d) => d as u8,
                _ => return Err(format!("non-digit char (base {base}): '{c}'")),
            };
            digits.push(d);
        }

        Ok(Num { digits, base })
    }

    pub fn divide(&self, dividend: u8) -> (Num, u8) {
        let mut quotient_digits: Vec<u8> = Vec::new();
        let mut remainder: u8 = 0;
        for &d in &self.digits {
            let accum = remainder * self.base + d;
            quotient_digits.push(accum / dividend);
            remainder = accum % dividend;
        }

        match quotient_digits.iter().position(|&x| x != 0) {
            Some(first_non_zero) => (
                Num {
                    digits: quotient_digits.split_off(first_non_zero), // remove leading zeros
                    base: self.base,
                },
                remainder,
            ),
            None => (Num::zero(self.base), remainder),
        }
    }
}
